6263. Dwarf tower

 

Little Vasya is playing a new game named “Dwarf Tower”. In this game there are n different items, which you can put on your dwarf character. Items are numbered from 1 to n. Vasya wants to get the item with number 1.

There are two ways to obtain an item:

·        You can buy an item. The i-th item costs ci money.

·        You can craft an item. This game supports only m types of crafting. To craft an item, you give two particular different items and get another one as a result.

Help Vasya to spend the least amount of money to get the item number 1.

 

Input. The first line contains two integers n and m (1 ≤ n ≤ 10000, 0 ≤ m ≤ 100000) – the number of different items and the number of crafting types.

The second line contains n integers ci (0 ≤ ci ≤ 109) – values of the items.

The following m lines describe crafting types, each line contains three distinct integers ai, xi, yi​, where ai is the item that can be crafted from items xi and yi (1 ≤ ai, xi, yi ≤ n, ai ≠ xi, xi ≠ yi, yi ≠ ai).

 

Output. Print a single integer – the least amount of money to spend.

 

Sample input 1

Sample output 1

5 3

5 0 1 2 5

5 2 3

4 2 3

1 4 5

2

 

 

Sample input 2

Sample output 2

3 1

2 2 1

1 2 3

2

 

 

SOLUTION

greedy

 

Algorithm analysis

Let’s build a graph – an adjacency list g, where g[i] contains pairs of numbers (j, a) such that from objects i and j it is possible to construct an object a: (i, j) → a.

Let cost be an array that initially contains the cost of purchasing items (cost[i] = ci). At the end of the algorithm, cost[i] will contain the least amount of money for which item i can be obtained.

 

Initially, all items are not processed (used[i] = 0).

While there is at least one not processed item

·                   Find an item a with the lowest cost;

·                   Apply all the rules listed in g[a];

·                   Mark the item a to be processed: used[a] = 0;

 

For each rule (a, b) → to from g[a] recompute

cost[to] = min(cost[to], cost[a] + cost[b])

 

Example

Consider the first test. There are 5 items with the following purchase costs:

There are three rules for constructing items. Build an adjacency list from them.

Item 2 has the lowest cost: cost[2] = 0. Apply the rules that involve item 2, namely the rules listed in g[2]. We mark item 2 as processed.

The next not processed item with the lowest price is 3. Apply the rules listed in g[3]. None of the prices changes.

The next not processed item with the lowest price is 4. Apply the rule in g[4].

In the next operations, the cost of items will not change. So the cost of getting item 1 is 2.

 

Algorithm realization

Declare the arrays. Declare an adjacency list g containing the rules for constructing objects.

 

vector<int> cost, used;

vector<vector<pair<int, int>>> g;

 

Read the input data. Initialize arrays.

 

scanf("%d %d", &n, &m);

g.resize(n + 1);

cost.resize(n + 1);

used.resize(n + 1);

 

Read the cost of buying items.

 

for (i = 1; i <= n; i++)

  scanf("%d", &cost[i]);

 

Read the rules for the items construction. Build an adjacency list from them.

 

for (i = 0; i < m; i++)

{

  scanf("%d %d %d", &a, &x, &y);

  g[x].push_back(make_pair(y, a));

  g[y].push_back(make_pair(x, a));

}

 

Initially all items are considered not processed.

 

for (i = 1; i <= n; i++)

  used[i] = 0;

 

for (k = 0; k < n; k++)

{

 

Among the not processed items, find one that has the lowest cost. Let it be an item number a.

 

  mn = 2e9; a = -1;

  for (i = 1; i <= n; i++)

    if (!used[i] && cost[i] < mn)

    {

      mn = cost[i];

      a = i;

    }

 

Mark an item a to be processed.

 

  used[a] = 1;

 

Iterate over the rules where an item a is involved.

 

  for (i = 0; i < g[a].size(); i++)

  {

    b = g[a][i].first;

    to = g[a][i].second; // (a, b) -> to

    if (cost[a] + cost[b] < cost[to]) cost[to] = cost[a] + cost[b];

  }

}

 

Print the least amount of money to buy the first item.

 

printf("%d\n", cost[1]);